package datastructure.list;

import java.util.Arrays;

/**
 * Description：
 * Author: zhangc
 * Date：2017/6/7 22:32
 */
public class ArrayList<T> implements List<T>, Iterable<T> {

    private Object[] elements;
    private int length = 0;
    private int capacity = 10;

    private double factor = 0.75;

    public ArrayList() {
        elements = new Object[ capacity ];
    }

    public ArrayList(int initCapacity) {
        this.capacity = initCapacity;
        elements = new Object[ capacity ];
    }

    public ArrayList(int initCapacity, double factor) {
        this.capacity = initCapacity;
        this.factor = factor;
        elements = new Object[ capacity ];
    }

    private void enlarge() {
        if (length + 1 > capacity * factor) {
            capacity = capacity + (capacity >> 1);
            elements = Arrays.copyOf(elements, capacity);
        }
    }

    @Override
    public void append(T element) {
        enlarge();
        elements[ length++ ] = element;
    }

    @Override
    public void insert(int index, T element) {
        enlarge();
        System.arraycopy(elements, index, elements, index + 1, length - index);
        elements[ index ] = element;
        length++;
    }

    @Override
    @SuppressWarnings("unchecked")
    public T get(int index) {
        if (index >= length || index < 0)
            throw new IllegalArgumentException("下标越界！！！！");
        return (T) elements[ index ];
    }

    @Override
    @SuppressWarnings("unchecked")
    public T remove(int index) {
        if (index < 0 || index >= length)
            throw new IllegalArgumentException("下标越界！！！！");
        Object temp = elements[ index ];
        System.arraycopy(elements, index + 1, elements, index, length - index - 1);
        length--;
        return (T) temp;
    }

    @Override
    public List<T> subList(int start, int end) {
        List<T> list = new ArrayList<>();
        for (int i = start; i < end; i++) {
            list.append(this.get(i));
        }
        return list;
    }

    @Override
    public void clear() {
        for (int i = 0; i < elements.length; i++) {
            elements[ i ] = null;
        }
        length = 0;
    }

    @Override
    public int length() {
        return length;
    }

    @Override
    public boolean contains(T element) {
        return false;
    }

    @Override
    public Iterator iterator() {
        return new Iterator();
    }

    @Override
    @SuppressWarnings("unchecked")
    public T[] toArray(T[] array) {
        if (array.length < length) {
            //这里的逻辑不是替换参数中的数组，而是返回一个新的数组。以array的类型构造
            //array = (T[]) Array.newInstance(array.getClass().getComponentType(), length);
            return (T[]) Arrays.copyOf(elements, length, array.getClass());
        }
        System.arraycopy(elements, 0, array, 0, length);
        if (array.length > length)
            array[ length ] = null;
        return array;
    }

    @SuppressWarnings("unchecked")
    public T[] toArray() {
        return Arrays.copyOf((T[]) elements, length);
    }

    private class Iterator implements java.util.Iterator<T> {
        private int index = 0;

        private Iterator() {
        }

        @Override
        public boolean hasNext() {
            return index < length();
        }

        @Override
        public T next() {
            return get(index++);
        }
    }

}
